A linked database (i.e., any database of documents containing mutual citations, such as the world wide web or other hypermedia archive) can be represented as a directed graph of N nodes, where each node corresponds to a document and where the directed connections between nodes correspond to directed links from one document to another. A given node has a set of forward links that connect it to children nodes, and a set of backward links that connect it to parent nodes.
Often it is useful to rank or assign importance values to the nodes. For example, the relevance of database search results can be improved by sorting the retrieved documents according to their ranks, and presenting the most important documents first. One approach to ranking is to determine the rank from the intrinsic content of a document, or from the anchor text of its parent documents. When the database has millions or billions of nodes, however, this approach becomes computationally prohibitive. Another more efficient approach is to determine the ranks from the extrinsic relationships between nodes, i.e., from the link structure of the directed graph. This type of approach is called link-based ranking. For example, U.S. Pat. No. 6,285,999 to Page discloses a link-based ranking technique used by the Google search engine for assigning ranks to web pages. The page rank is a measure of the importance of a page, recursively defined as a function of the ranks of its parent documents. Looked at another way, the rank of a web page is the steady-state probability that a web surfer ends up at the page after randomly following a large number of links. Thus, a page will tend to have a higher rank if it has many parent links, or if its parents themselves have high rank. The page ranks for the database are calculated by finding the principal eigenvector of an N×N link matrix A where each element aij of A represents a probability of moving from node i to node j of a directed graph of N nodes. The principal eigenvector may be computed using the power method, an iterative procedure that calculates the steady-state probability vector x defined as the vector to which xn=Anx0 converges as n grows very large, where x0 is an initial N-dimensional vector, e.g., a uniform distribution. The rank xk for a node k is simply the kth component of the vector x. A similar link-based ranking technique disclosed in U.S. Pat. No. 6,112,202 calculates the singular value decomposition of A and defines the rank of a node as the corresponding component of the singular vector. A simple but not very subtle technique ranks a node by simply counting the number of parent nodes it has.
Although these link-based ranking techniques are improvements over prior techniques, in the case of an extremely large database, such as the world wide web which contains billions of pages, the computation of the ranks for all the pages can take considerable time. Accordingly, it would be valuable to provide techniques for calculating page ranks with greater computational efficiency.